package main.剑指OfferⅠ;

public class Day31 {
    public static void main(String[] args) {//AC自动机
        System.out.println("剑指Offer14-Ⅱ.剪绳子Ⅱ");
        System.out.println("剑指Offer43.1~n整数中1出现的次数");
        System.out.println("剑指Offer44.数字序列中某一位的数字");
    }
}

class Offer14_Ⅱ{
    public int cuttingRope(int n) {
        final int MOD=(int)1e9+7;
        if (n==2) return 1;
        else if (n==3) return 2;
        long result=1;
        while (n>4){
            result=result*3;
            result=result%MOD;
            n-=3;
        }
        result=result*n;
        return (int)(result%MOD);
    }
}

class Offer43{
    public int countDigitOne(int n) {
        long mulk = 1;
        int ans = 0;
        for (int k = 0; n >= mulk; ++k) {
            ans += (n / (mulk * 10)) * mulk + Math.min(Math.max(n % (mulk * 10) - mulk + 1, 0), mulk);
            mulk *= 10;
        }
        return ans;
    }
}

class Offer44{
    public int findNthDigit(int n) {
        int digit=1;
        long start=1,count=9,num=0;
        while (n>count){
            n-=count;
            digit++;
            start*=10;
            count=digit*start*9;
        }
        num=start+(n-1)/digit;
        return Long.toString(num).charAt((n-1)%digit)-'0';
    }
}